1. Technical Field
The present invention relates to network interfacing and, more particularly, to methods and systems for transmitting data packets in a half-duplex network susceptible to capture effect.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling a network interface card at each station to share access to the media.
The Ethernet protocol ISO/IEC 8802-3 (ANSI/IEEE Std. 802.3, 1993 edition) defines a half-duplex media access mechanism that permits all stations to access the network channel with equality. Each station includes an Ethernet interface card that uses carrier-sense multiple-access with collision detection (CSMA/CD) to listen for traffic on the media. Transmission by a station begins after sensing a deassertion of a receive carrier on the media, indicating no network traffic. After starting transmission, a transmitting station will monitor the media to determine if there has been a collision due to another station sending data at the same time. If a collision is detected, both stations stop, wait a random amount of time, and retry transmission.
Any station can attempt to contend for the channel by waiting a predetermined transmission delay interval after the deassertion of the receive carrier on the media, known as the interpacket gap (IPG) interval. If a plurality of stations have data to send on the network, each of the stations will attempt to transmit in response to the sensed deassertion of the receive carrier on the media and after the IPG interval, resulting in a collision.
Ethernet network nodes mediate collisions using a truncated binary exponential backoff (TBEB) algorithm, which provides a controlled pseudorandom mechanism to enforce a collision backoff interval before retransmission is attempted. According to the truncated binary exponential backoff algorithm, a station keeps track of the number of transmission attempts (j) during the transmission of a current frame. The station computes a collision backoff interval as a randomized integer multiple of a slot time interval, and attempts retransmission after the collision backoff interval. The station will attempt to transmit under the truncated binary exponential algorithm a maximum of sixteen times.
The collision backoff interval is calculated by selecting a random number of slot times from the range of zero to 2.sup.j -1. For example, if the number of attempts j=3, then the range of randomly selected number of slot times is [0,7]; if the randomly-selected number of slot times is four, then the collision backoff interval will be equal to four slot time intervals. According to Ethernet protocol, the maximum range of randomly selected slot times is 2.sup.10 -1.
The truncated binary exponential algorithm has the disadvantage that the range of randomly selected slot times [0, 2.sup.j -1] increases exponentially each time a specific station loses a retry attempt after collision, resulting in a higher probability of losing the next collision mediation by randomly selecting a larger integer multiple of slot times. Thus, a new station that has data to transmit has a higher probability of winning a collision mediation than the station having a greater number of attempts. This effect is known as the capture effect, where a new station in the collision mediation effectively has a greater probability of capturing access to the media than the losing station until the maximum number of attempts has been reached.
Hence, collision-based networks having collision mediation require each colliding station to back off a random number of slot times, dependent on the number of attempts, before reattempting access to the medium. Such collision mediation reduces the network throughput and creates unbounded packet access latencies. Consequently, applications requiring bounded access latencies such as interactive multimedia cannot be supported on half-duplex networks.
The capture effect also may occur between network nodes having different capabilities in counting the transmission delay interval before attempting access of the media. Ethernet protocol specifies the transmission delay interval after sensed deassertion of the receive carrier, i.e., the interpacket gap (IPG) interval, as having a minimum value before stations can attempt access of the media. Network nodes (i.e., network nodes) that are capable of minimizing the transmission delay to the IPG interval, referred to as "fast nodes" or "dominant stations," will begin to transmit before stations incapable of achieving the minimum IPG interval, referred to as "slow nodes." In other words, hardware limitations may prevent the slow nodes from accessing the media within the time interval defined by the IPG interval. Hence, dominant network nodes will tend to capture the media over slower nodes that wait a longer time before attempting access of the media. These slower nodes encounter a surrender effect, in which they "surrender" their access to the media due to hardware limitations. The surrender effect may create substantial throughout problems in transmission protocols requiring a sender to receive an acknowledgement within a prescribed interval after a burst transmission.
Hence, capture effect may be caused by a station encountering a large number of collisions, variance in IPG access times between fast and slow nodes, and variations in propagation delay due to network topology. The capture effect thus causes a large variance in the network access latency, and a corresponding large variance in end to end delays experienced by data packets.
One proposed solution is described in Remakrishman et al., "The Ethernet Capture Effect: Analysis and Solution," IEEE Local Computer Networks (LCN) Conference, Minneapolis, Minn., October 1994, pages 228-240. The proposed solution by Ramakrishman, referred to as capture avoidance binary exponential backoff (CABEB), uses the standard binary exponential backoff with enhancements for collision resolution in a special case when a station attempts to capture the channel subsequent to an uninterrupted consecutive transmit period.
The CABEB algorithm modifies the truncated binary exponential backoff algorithm based on the premise that there can be no more than one station in an uninterrupted consecutive transmit state at any given time on a CSMA/CD local area network. The CABEB algorithm calculates the collision backoff interval for an uninterrupted consecutive transmission as follows: if the number of collision attempts equals 1, then the collision backoff interval equals two (2) slot time intervals; if the number of collisions equals 2, then the collision backoff interval equals zero (0) slot times; and if the number of collision attempts is greater than 2, then the conventional TBEB algorithm is followed.
Although the CABEB algorithm reduces the capture effect, implementation of the CABEB algorithm in small networks, such as a 2-station or 3-station Ethernet network, substantially increases the collision rate. The CABEB algorithm also reduces the network throughput, especially for small packets.
Another proposed media access mechanism, referred to as the Binary Logarithmic Access Method (BLAM), are described by the IEEE 802.3 w Working Group Draft, "Enhanced Media Access Control Algorithm for IEEE 802.3 CSMA/CD." However, BLAM requires substantial changes to the MAC, and has not been proven effective in a mixed environment having stations employing BLAM nodes and TBEB nodes.